#include<iostream>

//*
// * Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
 
class Solution {
public:
    TreeNode* ans = nullptr;
    bool isInTree(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (!root) return false;
        bool lson = isInTree(root->left, p, q);
        bool rson = isInTree(root->right, p, q);
        if ((lson && rson) || (p->val == root->val || q->val == root->val)) ans = root;

        return lson || rson || p->val == root->val || q->val == root->val;

    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        isInTree(root, p, q);
        return ans;
    }
};